package com.wujunshen.algorithm.leetcode.basic;

import java.util.Comparator;
import java.util.PriorityQueue;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

/**
 * @author frank woo(吴峻申) <br>
 *     email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/7/24 17:01<br>
 */
public class 合并两个有序链表 {
  public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    PriorityQueue<ListNode> queue = new PriorityQueue<>(2, Comparator.comparingInt(o -> o.val));

    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;

    if (list1 != null) {
      queue.add(list1);
    }

    if (list2 != null) {
      queue.add(list2);
    }

    while (!queue.isEmpty()) {
      tail.next = queue.poll();
      tail = tail.next;

      if (tail.next != null) {
        queue.add(tail.next);
      }
    }
    return dummy.next;
  }

  @Data
  @NoArgsConstructor
  @AllArgsConstructor
  static class ListNode {
    int val;
    ListNode next;

    ListNode(int value) {
      this.val = value;
    }
  }
}
